assoc(X,[],[]).
assoc(X,[[X|Y]|Z],[X|Y]) :- !.
assoc(X,[U|V],W) :- assoc(X,V,W).

eval([equal,X,X],←,true) :- !.
eval([equal,X,X1],U,true) :- eval(X,U,Y),eval(X,U1,Y),!.
eval([equal,X,X1],←,[]).
eval([atom,X],U,true) :- eval(X,U,Y1),atomic(Y1),!.
eval([atom,X],←,[]).
eval([null,X],U,true) :- eval(X,U,[]),!.
eval([null,X],←,[]).
eval([],←,[]).
eval([quote,Y],←,Y).
eval([car,X],U,Y) :- eval(X,U,[Y|←]).
eval([cdr,X],U,Y) :- eval(X,U,[←|Y]).
eval([cons,X,X1],U,[Y|Y1]) :- eval(X,U,Y),eval(X1,U,Y1).
eval([if,P,A,B],U,Y) :- eval(P,U,R),R=[],!,eval(B,U,Y).
eval([if,P,A,B],U,Y) :- eval(A,U,Y).
eval([[lambda,V,E],W],U,Y) :- eval(W,U,Y1),eval(E,[[V|Y1]|U],Y).
eval([F,Z],U,Y) :- eval(F,U,F1),eval([F1,Z],U,Y).
eval(V,U,Y) :- assoc(V,U,[V|Y]).

assertff :- asserta(eval(ff,←,[lambda,x,[if,[atom,x],x,[ff,[car,x]]]])).

assertalt :- asserta(eval(alt,←,[lambda,u,[if,[null,u],[],
[if,[null,[cdr,u]],u,[cons,[car,u],[alt,[cdr,[cdr,u]]]]]]])).

:-end.